//
// Created by 麻再挺 on 2021/12/14.
//

#include "bi_thr_tree.h"
#include "../stack_queue/queue.h"

/**
 * 线索前一节点, 线索化时需要使用
 */
BiThrTree *pre;

/**
 * 将二叉树线索化
 * @param p 线索二叉树
 */
void InThreading(BiThrTree *p);

/**
 * 按先序次序输入二叉树中结点的值, 空格字符表示空树
 * @param t 二叉树
 * @return
 */
Status CreateBiThrTree(BiThrTree *t) {
    // 从控制台获取数据
    char ch;
    scanf("%c", &ch);
    if (ch != ' ' && ch != '\n') {
//        if (!(t = malloc(sizeof(BiTree)))) exit(OVERFLOW);
        // 赋值, 生成根节点
        t->data = ch;
        t->lTag = LINK;
        t->rTag = LINK;
        if (!(t->lChild = malloc(sizeof(BiThrTree)))) exit(OVERFLOW);
        // 索引自加
        // 构造左子树
        CreateBiThrTree(t->lChild);
        if (!(t->rChild = malloc(sizeof(BiThrTree)))) exit(OVERFLOW);
        // 构造右子树
        CreateBiThrTree(t->rChild);
        // 如果左子树或右子树节点值为'\0', 则代表是空
        if (t->lChild->data == '\0') {
            free(t->lChild);
            t->lChild = NULL;
        }
        if (t->rChild->data == '\0') {
            free(t->rChild);
            t->rChild = NULL;
        }
    }
    return OK;
}

/**
 * 将二叉树按中序线索化
 * @param t 二叉树
 * @return
 */
Status InOrderThreading(BiThrTree *thrTree, BiThrTree *t) {
    // 建头节点
    thrTree->lChild = NULL;
    thrTree->rChild = thrTree;
    thrTree->lTag = LINK;
    thrTree->rTag = THREAD;
    thrTree->data = '\0';
    // 如果二叉树为空, 则左指针回指
    if (!t) {
        thrTree->lChild = thrTree;
    } else {
        // 左指针指向 t
        thrTree->lChild = t;
        // 赋值起始节点
        pre = thrTree;
        // 中序线索化
        InThreading(t);
        // 最后一个节点线索化
        pre->rChild = thrTree;
        // 右指针回指
        pre->rTag = THREAD;
        thrTree->rChild = pre;
    }
    return OK;
}

void InThreading(BiThrTree *p) {
    if (p) {
        // 左子树线索化
        InThreading(p->lChild);
        // 前驱线索
        if (!p->lChild) {
            p->lTag = THREAD;
            p->lChild = pre;
        }
        // 后继线索
        if (!pre->rChild) {
            pre->rTag = THREAD;
            pre->rChild = p;
        }
        // 保持 pre 指向 p 的前驱
        pre = p;
        // 右子树线索化
        InThreading(p->rChild);
    }
}

/**
 * 中序遍历
 */
Status InOrderThrTraverse(BiThrTree *t) {
    // 左节点
    BiThrNode *p = t->lChild;
    // 二叉树为空或遍历结束是 p == t;
    while (p != t) {
        while (p->lTag == LINK) p = p->lChild;
        printf("ltag: %d, data: %c, rtag: %d\t", p->lTag, p->data, p->rTag);
        while (p->rTag == THREAD && p->rChild != t) {
            // 访问后继结点
            p = p->rChild;
            printf("ltag: %d, data: %c, rtag: %d\t", p->lTag, p->data, p->rTag);
        }
        // 赋值后继结点
        p = p->rChild;
    }
    return OK;
}

/**
 * 层序遍历
 */
Status LevelOrderThrTraverse(BiThrTree *t) {
    // 初始化队列
    LinkQueue queue;
    Link_Queue_Init(&queue);
    // 将地址转换为整形值
    QElemType rootAddr = (QElemType) t;
    Link_Queue_Enter(&queue, rootAddr);
    BiThrTree *last = t;
    BiThrTree *nLast = t;
    // 循环打印
    while (!Link_Queue_Empty(&queue)) {
        // 出队
        QElemType root;
        Link_Queue_Deter(&queue, &root);
        BiThrTree tmp = (*(BiThrTree *) root);
        printf("ltag: %d, data: %c, rtag: %d\t", tmp.lTag, tmp.data, tmp.rTag);
        // 左子树
        if (tmp.lTag == LINK && tmp.lChild) {
            Link_Queue_Enter(&queue, tmp.lChild);
            nLast = tmp.lChild;
        }
        // 右子树
        if (tmp.rTag == LINK && tmp.rChild) {
            Link_Queue_Enter(&queue, tmp.rChild);
            nLast = tmp.rChild;
        }
        // 如果是最右侧节点, 则换行
        if (last == root) {
            printf("\n");
            last = nLast;
        }
    }
    return OK;
}










